package 数据结构.树;

/**
 * @author Zhu
 * @Description
 * @create 2023-02-27
 */
import java.util.*;
public class JZ27二叉树的镜像 {
    //递归
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        if(pRoot == null)
            return  null;
        TreeNode left = Mirror(pRoot.left);
        TreeNode right = Mirror(pRoot.right);

        pRoot.left = right;
        pRoot.right = left;
        return pRoot;
    }

    //非递归
    public TreeNode Mirror2 (TreeNode pRoot) {
        // write code here
        if(pRoot == null)
            return null;
        Stack<TreeNode> s = new Stack<>();
        s.push(pRoot);
        while (!s.isEmpty()){
            TreeNode node = s.pop();
            if(node.left!=null)
                s.push(node.left);
            if(node.right!=null)
                s.push(node.right);

            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return pRoot;
    }

    public TreeNode Mirror3 (TreeNode pRoot) {
        if(pRoot == null)
            return  null;
        Queue<TreeNode> q= new LinkedList<>();
        q.offer(pRoot);
        while (!q.isEmpty()){
            TreeNode node = q.poll();
            if(node.left!=null)
                q.offer(node.left);
            if(node.right!=null)
                q.offer(node.right);

            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return pRoot;
    }
}
